Ch 6 Queuing System

UTG

CPE 332

Computer Engineering

Mathematics II

Week 7

Part II, Chapter 6

Queuing System Continue

Extra: PRNG

Topics

• Single Server, M/M/1

• Kendal Notation

• Applications

Queuing System Case 3: Delay System Limited Server=N; With Unlimited Queue

x

ρ

λ < µ

p ; 0 ≤ x N

1

0

N

1



k

!

x

Nρ

ρ 

k

−λ

λ

p =

p

x

x

=

+

N

N

e

; 0

ρ

[

P k] =

N

N!( N − ρ)

k

k =

!

t / T

0

s

1

  p ; x N

[

P T

t] = e

; T =

k!

s

0

µ

 N!  N

Arrival Rate = λ

Departure Rate = µ

Customer

System, N Server

Customer

1.

สมมุติว่า Customer แต่ละคนที่เข ้ามาเป็น Poisson และได ้รับการ Service จากระบบทันที

2.

เวลาที่ใช ้ในการ Service เป็น Random สมมุติว่าเป็น Exponential ด ้วยเวลาเฉล่ีย T

3.

ระบบสามารถรับ Customer ได ้ไม่จํากัด แต่จะ Service ได ้สูงสุด N พร ้อมๆกัน

4.

ถ ้าทุก Server เต็ม Customer ใหม่จะต ้องรอใน Queue ในกรณีนี้จะเกิด Queuing Delay 5.

ระบบนี้เรียก M/M/N หรือ M/M/N/∞ แสดงได ้ด ้วย Simple Markov Model 6.

State Probability จะมีการกระจายแบบ Second Erlang (Erlang C) Distribution 0

1

2

N

N+1

p P = p P

i

ij

j

ji

Queuing System Case 3: Delay System Server=1; With Unlimited Queue; M/M/1

λ < µ 1

 ρ

−

p =

+1

=1− ρ

0

k

−λ

λ

 − ρ

e

1

(

)

[

P k] =

t / Ts

1

x

[

P T

t] = e

; T =

k!

s

p = ρ 1

( − ρ)

µ

x

Arrival Rate = λ

Departure Rate = µ

Customer

System, 1 Server

Customer

1.

สมมุติว่า Customer แต่ละคนที่เข ้ามาเป็น Poisson และได ้รับการ Service จากระบบทันที

2.

เวลาที่ใช ้ในการ Service เป็น Random สมมุติว่าเป็น Exponential ด ้วยเวลาเฉล่ีย T

3.

ระบบสามารถรับ Customer ได ้ไม่จํากัด แต่จะ Service ได ้ครั้งละคน

4.

ถ ้าทุก Server เต็ม Customer ใหม่จะต ้องรอใน Queue ในกรณีนี้จะเกิด Queuing Delay 5.

ระบบนี้เรียก M/M/1 หรือ M/M/1/∞ แสดงได ้ด ้วย Simple Markov Model 6.

State Probability จะมีการกระจายแบบ Second Erlang (Erlang C) Distribution 0

1

2

i

j

p P = p P

i

ij

j

ji

M/M/1: Summary

λ

µ=1/Ts

S

Arrival = Poisson, λ

Inter Arrival Time = Exponential, 1/λ

Service Rate, µ

Service Time, Ts (1/µ) = Exponential

Queue = FIFO

1 Server

Queuing Model(1 Server);

M/M/1

Queue = 0, No Delay

Queue = Delay

0

1

N+1

N+2

X

Server ว่าง Server Busy

1/Ts = service rate

arrival rate

For each server

λ

µ =1/ Ts

การทํางานของ M/M/1

State = 0

No Q Delay

Queue Empty

State = 1

Delay

State = x; Queue = infinity

Customer Wait in Q

State = x; x = Q+1

Severe Delay

Queue Overflow (Full)

กรณีที่

Congestion

Queue มีขนาดจํากัด = Q

Packet Lost

Kendal Notation

Kendal Notation

Kendal Notation

Analysis ય઼�શ઼ M/M/1

• สมมุติตอนแรกว่า Queue มีขนาดไม่จํากัด

• ใช ้ M/M/1 ในการ Model แต่ละ Port ของ Router (หรือ

Switch L3)

• Arrival คือจํานวน Packet ที่เข ้ามาในช่วงเวลาหนึ่ง ปกติ

วัดเป็น pps

• ขนาดของ Packet สมมุติว่าไม่แน่นอน แต่มีการกระจาย

แบบ Exponential

– Service Time ของแต่ละ Packet จะเป็น Exponential ด ้วย ทั้งนี้

ขึ้นอยู่กับค่า Link Speed ของ Output Port

• ค่า Server Utilization เท่ากับอัตราส่วนของ Arrival Rate หารด ้วย Service Rate จะบ่งบอกอัตราส่วนที่

Server จะ Busy และคือ Link Utilization ของ Output Port ด ้วย

ρ = λ / µ

Queuing in Communication

NW and M/M/1

Arrival Rate

Service Rate = 1/Service Time

λ

µ = 1/ Ts

ρ = λ / µ = λ Ts

Example

• Router ได ้รับ Packet เฉลี่ย 8 pps

– ความยาวของ Packet มีการกระจายแบบ Exponential ด ้วยความยาวเฉลี่ย 500 Octet

– Link ที่จะส่งออกไป มีความเร็ว 64 kbps

• 1. Arrival Rate,λ = 8 pps

• 2. ความยาวเฉลี่ยของ Packet = 4000 bit

• 3. ความเร็ว Link = 64 k ดังนั้น Service Time, Ts ของแต่ละ Packet = 4000/64k = 1/16

• 4. Service Rate(µ) = 16 pps

• 5. Server Utilization = 8/16 =0.5 = 50%

Assumption

• 1. อย่าลืมว่า Packet ที่เข ้ามา ต ้องเป็น

Independent และ Random มันจึงเป็น

Poisson

• 2. ความยาวของ Packet จะสมมุติว่าเป็น

Exponential ดังนั้น Service Time จะเป็น

Exponential ด ้วย แม ้ว่าสมมุติฐานนี้จะไม่

ถูกต ้องนัก

• 3. มี Output Link เดียว คือเป็น Single

Server

• 4. ดังนี้แล ้ว จึงจะเป็น M/M/1

Utilization

• Utilization บอกอัตราส่วนที่ Server จะ

Busy และสัมพันธ์กับ Probability ที่

Queue จะว่าง

– Probability ที่ Server ว่าง 1 − ρ

• ใน Network คือคือ Probability ที่

Output Link จะ Busy ด ้วย

ρ = λ / µ = λ Ts

Arrival Rate

• เนื่องจาก Arrival Rate มีการกระจายแบบ

Poisson ดังนั้นถ ้าให ้

λ เป็นอัตราเฉลี่ย

ของ Customer (Packet) ที่เข ้ามาใน

ช่วงเวลา 1 วินาที

– Probability ที่จะมี k customer (Packet) เข ้า

มาในช่วงเวลา T วินาทีจะหาได ้จาก

( T ) k −λ

λ

e T

p( X = k) = p( k) =

k!

−λ T

p( )

0 = e

Service Time

Ts เป็น Service Time เฉลี่ย และ Service Rate หาได ้จาก µ =1/ Ts

• เนื่องจาก Service Time เป็น Random

Variable ที่มีการกระจายแบบ Exponential

ดังนั้น Probability ที่ Service Time จะมี

ค่าน ้อยกว่า T จะเป็น

T / Ts

p t

( < T ) = 1 − e

Queue Distribution

• การกระจายของ Customer (State Probability)

สามารถคํานวณได ้จาก Probability ที่ ระบบ จะมี

k Packet อยู่ดังนี้

k

p = p T )

k

0

s

• โดยที่ p0 คือ Probability ที่ ระบบ จะว่าง

p = 1− ρ = 1− λ T

0

s

• ดังนั้น เราได ้

k

k

p = 1

( − λ T )(λ T ) = 1

( − ρ )ρ

k

s

s

• กล่าวคือ การกระจายของ Customer ในระบบ

หรือค่า State Probability จะเป็น Geometric

Distribution

લ઼�

�હ્યસ઼દ્ઘ� Customer હ્વ�����, N

લ઼�

�લ઼�

�હ્યસ઼દ્ઘ�ય઼�શ઼ State, 𝐸𝐸[𝑋𝑋]

จาก 𝑃𝑃 𝑋𝑋 = 𝑥𝑥 = 𝑝𝑝𝑥𝑥 = 1 − 𝜌𝜌 𝜌𝜌𝑥𝑥 เราได ้

𝐸𝐸 𝑋𝑋 = ∑∞

𝑥𝑥=0 𝑥𝑥 𝑝𝑝𝑥𝑥 = (1 − 𝜌𝜌) ∑𝑥𝑥=0 𝑥𝑥𝜌𝜌𝑥𝑥

แต่จาก (CPE231) ∑∞𝑥𝑥=0 𝑥𝑥𝜌𝜌𝑥𝑥−1 = 1

(1−𝜌𝜌)2

ดังนั้น

𝑋𝑋 = 1 − 𝜌𝜌 𝜌𝜌 ∑∞𝑥𝑥=0 𝑥𝑥𝜌𝜌𝑥𝑥−1 = 𝜌𝜌

1−𝜌𝜌

Queuing Delay

• จาก Geometric Distribution ค่าเฉลี่ย

คือจํานวน Customer เฉลี่ย คือจํานวน

Packet เฉลี่ยในระบบ จะหาได ้จาก

ρ

N = 1− ρ

• ถ ้าคิดเฉพาะจํานวน Customer เฉลี่ยใน

Queue เราจะได ้ ρ

ρ2

N = N − ρ =

− ρ =

Q

1 − ρ

1 − ρ

Queuing Delay

• สําหรับ Network ค่าเฉลี่ย จํานวน Packet

เฉลี่ยใน ระบบ และใน Queue จะหาได ้จาก

ρ

ρ 2

N =

N =

1 − ρ

Q

1− ρ

• ถ ้าแต่ละ Packet ต ้องใช ้เวลาเฉลี่ยในการ

Service

T

ดังนั้น ค่า

s

Queuing Delay

จะเป็น

ρ T

ρ

W =

s

=

1 − ρ

µ − λ

System Delay

• แต่ละ Packet ต ้องใช ้เวลาเฉลี่ยในการ

Service

T

ดังนั้น ค่า

s

Queuing Delay

จะเป็น

ρ T

ρ

W =

s

=

1 − ρ

µ − λ

• และเวลาเฉลี่ยทั้งหมดที่ลูกค ้าจะต ้องรอใน

ระบบทั้งหมดจะเป็น

ρ

T = W + T =

+ 1 = 1

s

µ − λ µ µ − λ

Little’s Theorem

• ถ ้า T เป็นเวลาเฉลี่ยที่ลูกค ้าอยู่ในระบบ และ

λ เป็น Arrival Rate ดังนั้นจํานวนลูกค ้า

เฉลี่ยในระบบจะเท่ากับ

N = λ T

N = λ W

Q

สรุป M/M/1

สรุป M/M/1

สรุป M/M/1

M/M/1 Example 1

6 5 4 3 2 1

λ = ?

µ = ?

S

M/M/1 Example 1

M/M/1 Example 1

M/M/1 Example 1

M/M/1 Example 1

M/M/1 Example 2

λ = ?

µ = ?

M/M/1 Example 2

4.ธนาคารต้องจัดท่ีน่ังก่ีท่ี(รวมท่ีน่ังตอนใช้บริการ)เพ่ือจะ

ให้แน่ใจว่าอย่างน้อย 80% ของผู้ท่ีเข้ามาจะได้น่ัง

4.ธนาคารต้องจัดท่ีน่ังก่ีท่ี(รวมท่ีน่ังตอนใช้บริการ)เพ่ือจะ

ให้แน่ใจว่าอย่างน้อย 80% ของผู้ท่ีเข้ามาจะได้น่ัง

𝑥𝑥 = 9

M/M/1 Example 3

M/M/1 Example 3

M/M/1 Example 3

End of Chapter 6

• HW6 Due Monday Noon

– ส่งที่พี่หนึ่งเท่านั้น ก่อนเที่ยง จันทร์ 29 ก.พ.

– ใส่ตะกร ้า หน ้าโต๊ะ Counter อย่าส่งผิดที่

– เฉลยจะประกาศวันถัดไปบน Web

• Next

– Random Number Generator

– Preparation for Midterm Exam

Topics

• Random Number and Properties

• Random Number Test

• Pseudo Random Number Generator

MT Exam Preparation

Random Number

• Random Number เป็น Set ของตัวเลขที่

สุ่มขึ้นมาแบบอิสระ(Random) และไม่ขึ้นต่อ

กัน (Independent) โดยมีค่าการกระจาย

(Distribution) ของชุดตัวเลข ตามที่

กําหนดแบบใดแบบหนึ่ง

• เลขแต่ละตัวที่สุ่มจะต ้องไม่มีความสัมพันธ์

กัน ทดสอบได ้จากค่า Correlation

મ઼��હ્વહ઼�

શ઼�� Random Number

• Gambling

• Statistical Sampling

• Simulation

• Cryptography

• Computer Games

• Hash Algorithm/Searching Algorithm

Random Number Generation

• เป็นอุปกรณ์ที่ใช ้เป็นตัวกําเนิดชุดของตัวเลข

Random ที่ต ้องการ

– True Random Number Generator(TRNG)

• ประกอบด ้วยอุปกรณ์ทาง Physic ที่ใช ้กําเนิดตัวเลข

• มักจะได ้จากแหล่งกําเนิดของ Noise ที่เกิดตาม

ธรรมชาติ

– Thermal Noise/Shot Noise/Radioactive

• หรือใช ้ Roulette Wheel

– Pseudo Random Number Generator(PRNG)

• Computational Algorithm จากสมการทาง

คณิตศาสตร์ โดยเริ่มจากตัวเลข “Seed”

• มีคุณสมบติเหมือนกับเป็น Random แต่มี Period และ

สามารถคํานวณล่วงหน ้าตามสมการได ้

PRNG: Pseudo Random Number Generator: Linear Congruential Generator

• เริ่มจาก “Seed”, 𝑋𝑋0 และคํานวณ Series

𝑋𝑋1, 𝑋𝑋2, 𝑋𝑋3, … จากสมการ Recurrence

𝑋𝑋𝑛𝑛+1 = 𝑎𝑎𝑋𝑋𝑛𝑛 + 𝑏𝑏 𝑚𝑚𝑚𝑚𝑚𝑚 𝑚𝑚

– a, b และ m เป็น Integer ปกติจะมีขนาดใหญ่; จํานวนเลขสูงสุด

ที่ไม่ซํ้ากันจะถูกกําหนดด ้วยค่า Modulus m

• Sequence ที่ได ้จะมีค่าระหว่าง [0,m) หรือ 0 ≤ 𝑋𝑋 < 𝑚𝑚

• Seed 𝑋𝑋0; 0 ≤ 𝑋𝑋0 < 𝑚𝑚

• Multiplier 𝑎𝑎; 0 < 𝑎𝑎 < 𝑚𝑚

• Increment 𝑏𝑏; 0 ≤ 𝑏𝑏 < 𝑚𝑚

• ถ ้า b = 0 เราเรียก Multiplicative Congruential Generator หรือ Lehmer Generator มิฉะนั้นแล ้วเราเรียก Mixed Congruential Generator

– ตัวเลขที่ได ้จะมีการกระจายแบบ Uniform ถ ้าต ้องการการกระจาย

แบบอื่น จะใช ้การ Transformation

– Algorithm นี้เรียก LCG หรือ Linear Congruential Generator เป็นวิธีที่ง่ายในการสร ้าง PRN

Period of LCG

• Period มีค่าได ้สูงสุดคือ m เรียก Full

Period

– บางกรณีจะได ้น้อยกว่านั้น ขึ้นอยู่กับการเลือกค่า

‘a’ และในกรณีที่ b=0

• Generator จะมี Full Period ก็ต่อเมื่อ

(Hull-Dobell Theorem)

– 1. b และ m เป็น Relative Prime

– 2. a-1 จะต ้องสามารถหารได ้ด ้วยทุกๆ factor ที่เป็นค่า prime ของ m

– 3. a-1 จะต ้องหารได ้ด ้วย 4 ถ ้า m หารได ้ด ้วย 4

Parameters used

• ส่วนใหญ่จะใช ้ LCG ที่ m มีค่าเป็นกําลังของ

2 ที่นิยมมากสุดคือ 232 และ 264

– MS Visual C++ ใช ้ m=232,

a=214013,b=2531011

– MS Visual Basic 6 ใช ้ m=224,

a=1140671485,b=12820163

લ઼�

ઙ્ખ દ્ભઢ્ઢ��

ઙ્ઘ�

LCG

• มีข ้อดีคือคํานวณได ้ง่าย แต่ให ้ Series ของ

Random Number ที่มีคุณสมบัติพอประมาณ

เท่านั้น เพราะให ้ค่า Serial Correlation สูง

– ไม่เหมาะกับการนําไปใช ้ใน Monte Carlo

Simulation

– ไม่เหมาะกับการนําไปใช ้ใน Cryptography

• สามารถสร ้างได ้จากวงจร Linear Feedback

Shift Register(LFSR)

– ปกติวงจรนี้จะผลิต Stream ของ bit

• ได ้ Uniform Distributed PRNG

PRNG ��� હ્યહ઼�

• Blum Blum Shub

• Wichmann-Hill

• Multiply with Carry

• Mersenne Twister (นิยมมากสุด)

• Park-Miller

• RC4

• Rule 30

Randomness Test

• เพื่อหา Pattern ในชุด หรือ Series ของตัวเลข

– ซึ่งไม่ควรจะมีอยู่ถ ้าชุดตัวเลขเป็น Random และ

Independent อย่างแท ้จริง

• ใช ้ในการทดสอบ และเปรียบเทียบ Algorithm ต่างๆ

ที่ใช ้ผลิต PRNG โดยใช ้พื้นฐานจาก

– Statistical Test ทดสอบจากคุณสมบัติทางสถิติ

Diehard Tests ประกอบด ้วยชุดของ Test

TestU01 library ประกอบด ้วย utilities สําหรับ

statistical testing ของ uniform RNG

– Transform ดูคุณสมบัติเมื่อ Transform

• Hadamard Transform(Generalized FT)

– Complexity ความซับซ ้อนของตัวเลข

• Kolmogorov complexity

Midterm Preparation

• เก็บ 35 เปอร์เซ็นต์

• ไม่มีการ Make Up

• สอบ 3 ชั่วโมง บทที่ 1-6

– Monday 7 March; 13:30 – 16:30

• ต ้องใช ้เครื่องคิดเลข

– รุ่นตามที่คณะประกาศเท่านั้น ห ้ามใช ้อุปกรณ์อื่นๆ

• สมการที่สําคัญจะให ้มา ไม่ต ้องจํา

6 ข้อ บทละ 1 ข้อ รวม 6 ข้อ เลือกทํา 5 ข้อ

5 ข้อ 50 คะแนน คิดเป็น 35 %

สมการที่ให้

ในการสอบ MT

Review દ્મ�

દ્ધય઼�

���મ઼દ્ભ��

• Chapter 1: Vector

– Magnitude/Direction/Unit Vector

– Direction Cosine

– Component Vector/Position Vector

– Dot/Cross Product and Properties

– Equation of Line and Plane, Angle of Vectors

• Chapter 2: Matrices

– Types of Matrices, Minor, Cofactor, Diagonal

– Determinant by Expansion

– Inverse of Matrix

– Rank/Reduced Matrix (Process of Elimination)

– Homogeneous/Non Homogeneous Linear Eq.

Review દ્મ�

દ્ધય઼�

���મ઼દ્ભ��

• Chapter 3: Eigen Value/Vector/Diag

– Eigenvalues

– Eigenvectors

– Diagonalization

– Symmetric/Orthogonal Matrix

• Chapter 4: Probability

– Conditional Probability/Bayes Rule

– Random Variable

– CDF/PDF/PMF; Poisson/Exponential Distribution

– Expectation Concept

– Mean, Mean Square, Variance

– Joint Random Variable, Correlation/Covariance

Review દ્મ�

દ્ધય઼�

���મ઼દ્ભ��

• Chapter 5: Random Process

– Stationary/Ergodic

– Autocorrelation/Cross Correlation

– Counting/Poisson Process/Birth and Death Process

– MarKov Model; Global Balanced Equation

– Simple MarKov Model; Detail Balanced Equation

• Chapter 6: Queuing System

– M/M/1 Concept

– Arrival Rate/Inter Arrival Time

– Departure Rate/Service Time

– Utilization, P[X=k], P[X<=k]

– Average Customer(System/Q), Time(System/Q)

Document Outline

Table of contents

previous page start